package com.xxd.algo.newcode.mid01.class05;

import java.util.TreeSet;

/**
 * @author: XiaoDong.Xie
 * @create: 2021-10-17 19:45
 */
public class Code03_MaxSubArraySumLessOrEqualK {

    public static int getMaxLessOrEqualK(int[] arr, int K) {
        TreeSet<Integer> set = new TreeSet<>();
        set.add(0);

        int sum = 0;
        int max = Integer.MAX_VALUE;

        // 每一步的i，都求子数组必须以i结尾的情况下，求子数组的累加和 是 <= K 的，并是最大的
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            if (set.ceiling(sum - K) != null) {
                max = Math.max(max, sum - set.ceiling(sum - K));
            }
            set.add(sum);
        }

        return max;
    }
}
